NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

Title: Graph Coloring using ABT kernel - derived in Asynchronous Backtracking-Yokoo)
Author: Ionel Muscalagiu, Jose M. Vidal
Description:
This is the implementation of the ABT kernel - derived in Asynchronous Backtracking, for the graph coloring problem. We solve the graph coloring problem using the ABT kernel algorithm (derived in Asynchronous Backtracking ) from
<ul>
C. Bessiere, I. Brito, A. Maestre, P. Meseguer.
<a href="www.lirmm.fr/~bessiere/stock/aij05.pdf ">
"Asynchronous Backtracking without Adding Links: A New Member in the ABT Family"
</a>.
Artificial Intelligence, volume 161, pages 7-24.
</ul>
In this paper, it is presented a general framework for solving DCSP-s, framework which we will refer to as ABT kernel. The ABT kernel algorithm, a new ABT-based algorithm that does not require to add communication links between initially unconnected agents. The ABT kernel algorithm is sound but may not terminate(the ABT kernel may store obsolete information). We start at this procedure, which forms the basic centre or the unifying framework, we could reach the known algorithms or versions close to this ( such as Yokoo's ABT or a correct version of DIBT, DisDB).
A first way to remove obsolete information is to add new communication links to allow a nogood owner to determine whether this nogood is obsolete or not. These added links were proposed in the original ABT algorithm .
A second way to remove obsolete information is to detect when a nogood could become obsolete. In that case, the hypothetically obsolete nogood and the values of unrelated agents are forgotten. These two alternative ways lead to the following four algorithms :
-Adding links as preprocessing: ABTall (DIBT). This algorithm adds all the potentially useful new links during a preprocessing phase. New links are permanent.
- Adding links during search: Yokoo's ABT. This algorithm adds new links between agents during search. A link is requested by self when it receives a Back message containing unrelated agents above self in the ordering. New links are permanent.
- Adding temporary links: ABTtemp. This algorithm adds new links between agents during search, as ABT. The dierence is that new links are temporary. A new link remains until a xed number of messages have been exchanged through it. After that, it is removed.
- No links: ABTnot - Distributed Dynamic Backtracking. No new links are added between agents. To achieve completeness, this algorithm has to remove obsolete information in fnite time. To do so, when an agent backtracks it forgets all nogoods that hypothetically could become obsolete.